package cn.chen.算法.排序;

import java.util.Arrays;

/**
 * 基数排序：
 *  从最低位开始比较每一位数，然后将比较之后的数按照从最低位从小到大排序，
 *  以此类推
 *
 */
public class RedixSort {

    public static void main(String[] args){

        int[] arr={521,10,286,495,1,73,1000};

        System.out.println(Arrays.toString(arr));
        redixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void redixSort(int[] arr){

        // 该循环是为了得到最大值，以便于得到最大数的长度
        int max=0;
        for(int i=0;i<arr.length;i++){

            if(max<arr[i])
                max=arr[i];
        }
        int maxLength=(max+"").length();

        int[][] tong=new int[10][arr.length];   // 每一个一维数组都是一个桶，一共10个桶
        int[] count=new int[10];    // 用来存放桶中存放元素的个数,索引对应的就是桶，值就是该通存放的元素个数

        for(int i=1;i<=maxLength;i++){

            for(int j=0;j<arr.length;j++){  // 遍历要排序的数组

                int num=arr[j]/(int)Math.pow(10,(i-1)) %10; // 得到每个元素的每一位数

                // count[num]代表的就是num这个桶已经装了多少个元素了，从0开始
                tong[num][count[num]++]=arr[j]; // 将该元素存放在桶中，这里的count[num]++，++在后面，是因为数组的该值默认是从0开始，数组索引从0开始
            }
            // 上面循环结束代表，已经将这一个数的顺序整理出来了
            // 下面就将数据取出来放在arr中，准备进行下一位数的比较
            int index=0;    // 用来标记arr数组的索引
            for(int j=0;j<count.length;j++){

                if(count[j]!=0){    // 根据对应索引的值判断index对应的桶中是否存有数据

                    for(int k=0;k<count[j];k++){

                        arr[index++]=tong[j][k];
                    }
                    count[j]=0; // 清空该桶
                }
            }
        }
    }
}
